package com.arron.algorithm.leetcodetop100.动态规划.背包问题;

/**
 *  暴力回溯:
 * @see com.arron.algorithm.leetcodetop100.回溯.目标和
 *
 *   https://leetcode.cn/problems/target-sum/solutions/328335/dong-tai-gui-hua-he-hui-su-suan-fa-dao-di-shui-shi/
 */
public class 目标和 {



    /**
     *  假设 选择 + 号的数和为sum(A)
     *  设 选择 - 的个数和为sum(B)
     *  则有 sum(A) -sum(B) = target
     *  sum(A) = target+ sum(B)
     *  sum(A) + sum(A) = target + sum(B) + sum(A)
     *  sum(A) = (target + sum(nums))/2
     *   即转换为 分割和子集问题
     * @see 分割等和子集
     */

        public int findTargetSumWays(int[] nums, int target) {

            int sum = 0;

            for (int i = 0; i < nums.length; i++) {
                sum +=nums[i];
            }
            if (sum < Math.abs(target)){
                return 0;
            }
            if ((target + sum)%2 !=0){
                return 0;
            }


            //定义dp dp[i][j] ,表示前i个物品，凑成和为 j的方法数
            int n = nums.length;
            int w = (sum+target)/2;
            int[][] dp = new int[n+1][w+1];

            //base case
            for (int i = 0; i <= w; i++) {
                dp[0][i] = 0;
            }
            for (int i = 0; i <= n; i++) {
                dp[i][0] = 1;
            }

            for (int i = 1; i <= n ; i++) {
                // 这里要从0开始，因为当物品重量为0 时可以有多种装法
                for (int j = 0; j <= w ; j++) {
                    if (j-nums[i-1] <0){
                        dp[i][j] = dp[i-1][j];
                    }else {
                        dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i-1]];
                    }
                }
            }
            return dp[n][w];
        }



    public static void main(String[] args) {

        目标和 findTarget = new 目标和();
        int[] nums = {0,0,0,0,0,0,0,0,1};
        System.out.println(findTarget.findTargetSumWays(nums, 1));
    }

}
